package com.arron.algorithm.sort;


import java.util.Arrays;

/**
 * 插入排序
 *  最坏时间复杂度 ：O(n2)
 *  最好时间复杂度 ：O(n)
 *
 *
 */
public class InsertionSort {




    public static void main(String[] args) {
        int[] array = {2,3,1,0,98};

        long timeMillis = System.currentTimeMillis();

        sort(array);
        System.out.println("============耗时："+(System.currentTimeMillis()-timeMillis));
        Arrays.sort(array);
        print(array);

    }


    public static void sort(int[] array){

        if (array == null || array.length <2){
            return;
        }

        int j= 0; //记录插入的位置下标
        int current = 0;//记录移动的元素
        for (int i = 1; i < array.length; i++) {

            current = array[i];

            for (j = i-1; j >=0 ; j--) {
                if (array[j]>current){
                    //如果
                    array[j+1] = array[j];

                }else {
                    //找到合适的位置插入
                    break;
                }
            }
            System.out.println("j == "+j);
            //跳出循环说明找到了合适的插入位置
            array[j+1]  = current;
        }


    }

    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }



}
